//#include "StdAfx.h"
#include "generator-support.h"

#include <algorithm>
#include <gtest/gtest.h>
#include <boost/graph/graphml.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/foreach.hpp>
#include "macros.h"

#include <boost/random.hpp>
#include <boost/random/uniform_int.hpp>

#define foreach BOOST_FOREACH

using namespace boost;

namespace cccn {

////////////////////////////
//                        //
// Graph class definition //
//                        //
////////////////////////////

/**
 * Always return the same edge from two node IDs, regardless of their direction
 */
Graph::Edge_t
MakeEdge (uint a, uint b)
  {
  if (a < b)
    return Graph::Edge_t (a, b);
  else
    return Graph::Edge_t (b, a);
  }

Graph::Vertex_t 
Graph::AddVertex (uint n)
  {
  while (n >= num_vertices (m_graph))
    {
    add_vertex (m_graph);
    }

  Graph::Vertex_t v = vertex (n, m_graph);
  put (vertex_index, m_graph, v, n);
  return v;
  }

Graph::Graph () : m_graph ()
  {
  m_graph.clear ();
  }

bool 
Graph::Connect (uint a, uint b)
  {
  // do not allow adding self-looping edges
  if (a == b)
    {
    return false;
    }
  Graph::Vertex_t v_a, v_b;
  v_a = AddVertex (a);
  v_b = AddVertex (b);
  return add_edge (v_a, v_b, m_graph).second;
  }

void 
Graph::Disconnect (uint a, uint b)
  {
  Vertex_t v_a = vertex (a, m_graph);
  Vertex_t v_b = vertex (b, m_graph);
  remove_edge (v_a, v_b, m_graph);
  }

const BoostGraph_t& 
Graph::GetBoostGraph () const
  {
  return m_graph;
  }

BoostGraph_t& 
Graph::GetBoostGraph ()
  {
  return m_graph;
  }

/////////////////////////////////
//                             //
// Global function definitions //
//                             //
/////////////////////////////////

uint 
GetGirth (const Graph& g)
  {
  const BoostGraph_t& boost_g = g.GetBoostGraph ();
  return boost_g[graph_bundle].girth;
  }

uint 
GetSize (const Graph& g)
  {
  const BoostGraph_t& boost_g = g.GetBoostGraph ();
  return num_vertices (boost_g);
  }

///////////////////////////////////
//                               //
// GraphMeasure class definition //
//                               //
///////////////////////////////////

GraphMeasure::GraphMeasure (const Graph& g) : m_graph (g.GetBoostGraph ())
  {}

uint 
GraphMeasure::NumberOfNodes () const
  {
  return num_vertices (m_graph);
  }

uint 
GraphMeasure::NumberOfEdges () const
  {
  return num_edges (m_graph);
  }

list<uint> 
GraphMeasure::GetNeighborsOf (uint n) const
  {
  typedef boost::graph_traits<BoostGraph_t>::adjacency_iterator adjacency_iterator;    

  // get all adjacency vertices of n
  Vertex_t v = vertex (n, m_graph);
  pair<adjacency_iterator, adjacency_iterator> adjv_it = adjacent_vertices (v, m_graph);

  // get the node ids of all adjacency vertices
  list<uint> all_adjv_id;
  while (adjv_it.first != adjv_it.second)
    {
    Vertex_t adjv = *adjv_it.first;
    uint adjv_id = get (vertex_index, m_graph, adjv);
    all_adjv_id.push_back (adjv_id);

    adjv_it.first++;
    }

  return all_adjv_id;
  }

uint 
GraphMeasure::DegreeOf (uint n) const
  {
  Vertex_t v = vertex (n, m_graph);
  return boost::out_degree (v, m_graph);
  }

/////////////////////////////////
//                             //
// Public functions definition //
//                             //
/////////////////////////////////

ostream& 
operator<< (ostream& os, const Graph::Edge_t& e)
  {
  os << "(" << e.first << "," << e.second << ")" << ends;
  return os;
  }

string 
GetOnlyFilename (string name)
  {
  if (name.find ('\0') != string::npos)
    {
    name.erase (name.find ('\0'), 1);
    }
  if (name.find (GRAPH_EXTENSION) != string::npos)
    {
    name.erase (name.find (GRAPH_EXTENSION));
    }
  if (name.find_last_of ('/') != string::npos)
    {
    name.erase (0, name.find_last_of ('/')+1);
    }

  return name;
  }

void 
ChangeGraphOutName (string& graphml, string name)
  {
  name = GetOnlyFilename (name);
  string::size_type location = graphml.find ("<graph label=\"") + strlen ("<graph label=\"");
  graphml.replace (location, 1, name);
  }

void 
ExportXgmml (ostream& os, BoostGraph_t& g)
  {
  typedef boost::graph_traits<BoostGraph_t>::vertex_descriptor Vertex_t;
  typedef boost::graph_traits<BoostGraph_t>::vertex_iterator Vertex_It_t;
  typedef boost::graph_traits<BoostGraph_t>::edge_iterator Edge_It_t;

  os <<
  "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"yes\"?>" << endl <<
  "<graph label=\"G\" xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\" xmlns:cy=\"http://www.cytoscape.org\" xmlns=\"http://www.cs.rpi.edu/XGMML\"  directed=\"1\">" << endl <<
  "  <att name=\"documentVersion\" value=\"1.1\"/>" << endl <<
  "  <att name=\"networkMetadata\">" << endl <<
  "    <rdf:RDF>" << endl <<
  "      <rdf:Description rdf:about=\"http://www.cytoscape.org/\">" << endl <<
  "        <dc:description>N/A</dc:description>" << endl <<
  "        <dc:identifier>N/A</dc:identifier>" << endl <<
  "        <dc:format>Cytoscape-XGMML</dc:format>" << endl <<
  "      </rdf:Description>" << endl <<
  "    </rdf:RDF>" << endl <<
  "  </att>" << endl <<
  "  <att type=\"string\" name=\"backgroundColor\" value=\"#ffffff\"/>" << endl;
  //"  <att type=\"real\" name=\"GRAPH_VIEW_ZOOM\" value=\"1.3078261337489379\"/>" << endl <<
  //"  <att type=\"real\" name=\"GRAPH_VIEW_CENTER_X\" value=\"130.99999809265137\"/>" << endl <<
  //"  <att type=\"real\" name=\"GRAPH_VIEW_CENTER_Y\" value=\"134.00000095367432\"/>" << endl <<
  if (g[graph_bundle].girth > 0)
    {
    os << "  <att type=\"integer\" name=\"girth\" value=\"" << g[graph_bundle].girth << "\"/>" << endl;
    }
  if (g[graph_bundle].sumGirth > 0)
    {
    os << "  <att type=\"integer\" name=\"sum girth\" value=\"" << g[graph_bundle].sumGirth << "\"/>" << endl;
    }
  if (g[graph_bundle].avgDistance > 0)
    {
    os << "  <att type=\"real\" name=\"avg distance\" value=\"" << g[graph_bundle].avgDistance << "\"/>" << endl;
    }
  if (g[graph_bundle].syncValue > 0)
    {
    os << "  <att type=\"real\" name=\"syncValue\" value=\"" << g[graph_bundle].syncValue << "\"/>" << endl;
    }
  if (g[graph_bundle].syncRatio > 0)
    {
    os << "  <att type=\"real\" name=\"syncRatio\" value=\"" << g[graph_bundle].syncRatio << "\"/>" << endl;
    }

  // go through all vertices and the associated properties
  Vertex_It_t v_begin, v_end;
  tie (v_begin, v_end) = vertices (g);
  for (Vertex_It_t it = v_begin; it != v_end; it++)
    {
    uint v_id = get (vertex_index, g, *it);
    uint v_girth = get (vertex_girth, g, *it);
    ostringstream v_label;
    v_label << GetOnlyFilename (g[graph_bundle].name) << '-' << v_id;

    os <<
    "  <node label=\"" << v_label.str () << "\" id=\"-" << v_id+1 << "\">" << endl <<
    "    <att type=\"string\" name=\"canonicalName\" value=\"n" << v_id << "\"/>" << endl <<
    "    <att type=\"integer\" name=\"girth\" value=\"" << v_girth << "\"/>" << endl <<
    "    <graphics type=\"ELLIPSE\" h=\"25.0\" w=\"25.0\" fill=\"#99ff99\" width=\"2\" outline=\"#009900\" cy:nodeTransparency=\"0.5\" cy:nodeLabelFont=\"SansSerif.bold-0-12\" cy:borderLineType=\"solid\"/>" <<
    "  </node>" << endl;
    }

  Edge_It_t e_begin, e_end;
  tie (e_begin, e_end) = edges (g);
  for (Edge_It_t it = e_begin; it != e_end; it++)
    {
    Vertex_t src = source (*it, g);
    Vertex_t tgt = target (*it, g);
    uint src_id = get (vertex_index, g, src);
    uint tgt_id = get (vertex_index, g, tgt);

    os <<
    "  <edge label=\"n" << src_id << " (pp) n" << tgt_id << "\" source=\"-" << src_id+1 << "\" target=\"-" << tgt_id+1 << "\">" << endl <<
    "    <graphics width=\"2\" fill=\"#333333\" cy:sourceArrow=\"0\" cy:targetArrow=\"0\" cy:sourceArrowColor=\"#000000\" cy:targetArrowColor=\"#000000\" cy:edgeLabelFont=\"Default-0-10\" cy:edgeLineType=\"SOLID\" cy:curved=\"STRAIGHT_LINES\"/>" <<
    "  </edge>" << endl;
    }
  os << 
  "</graph>" << endl;
  }

ostream& 
operator<< (ostream& os, const Graph& _g)
  {
  BoostGraph_t g = _g.m_graph;

  ostringstream gss;
  ExportXgmml (gss, g);

  string gstr = gss.str ();
  if (!g[boost::graph_bundle].name.empty ())
    {
    ChangeGraphOutName (gstr, g[boost::graph_bundle].name);
    }
  os << gstr;
  return os;
  }

uint 
RandomInt (uint maxInt)
  {
  // random number generation engine
  static taus88 randeng;

  return uniform_int<uint> (0, maxInt).operator () (randeng);
  }

}; // namespace cccn

/////////////
// Testing //
/////////////

using namespace cccn;

/*
 * Test passed when two edges are equal regardless of their direction
 */
TEST (EdgeTest, IgnoreDirectionalTest)
  {
  EXPECT_EQ (MakeEdge (0, 1), MakeEdge (1, 0));
  EXPECT_EQ (MakeEdge (0, 1), MakeEdge (0, 1));
  }

namespace cccn
{

class GraphTest : public ::testing::TestWithParam <uint>
  {};

TEST_P (GraphTest, AddVertexTest)
  {
  typedef Graph::Vertex_t Vertex_t;
  const uint n = GetParam ();

  Graph g;

  for (uint expect_id=0, g_size=1; expect_id<n; expect_id++, g_size++)
    {
    Vertex_t v = g.AddVertex (expect_id);
    uint actual_id = get (vertex_index, g.m_graph, v);

    EXPECT_EQ (expect_id, actual_id);
    EXPECT_EQ (g_size, num_vertices (g.m_graph));
    }
  }

} // namespace cccn

/*
 * Test passed if a simple graph can be built
 */ 
TEST_P (GraphTest, BuildRingTest)
  {
  const uint n = GetParam ();
  Graph g;
  for (uint i=0; i<n; i++)
    {
    EXPECT_TRUE (g.Connect (i, (i+1)%n)) << "failed to connect the edge (" << i << "," << (i+1)%n << ") for a ring with size = " << n;
    }

  DEBUG_PRINT_GRAPH ("ring-" << n, g);

  GraphMeasure gm (g);
  EXPECT_EQ (n, gm.NumberOfNodes ()) << "where n is the expected number of nodes";
  EXPECT_EQ (n, gm.NumberOfEdges ()) << "where n is the expected number of nodes";

  for (uint j=0; j<n; j++)
    {
    g.Disconnect (j, (j+1)%n);
    }

  EXPECT_EQ (n, gm.NumberOfNodes ()) << "all nodes should remain unchanged";
  EXPECT_EQ (0, gm.NumberOfEdges ()) << "all edges should be removed. n = " << n;

  DEBUG_PRINT_GRAPH ("empty-ring-" << n, g);
  }

INSTANTIATE_TEST_CASE_P (RingSize, GraphTest, ::testing::Range<uint> (20, 61, 10));

TEST (GraphTest, NoSelfLoopTest)
  {
  Graph g;
  EXPECT_TRUE (g.Connect (0, 1));
  EXPECT_FALSE (g.Connect (0, 0));
  EXPECT_FALSE (g.Connect (1, 1));
  }

/* 
 * Test passed if adding duplicated edges can be detected
 */
TEST (GraphTest, DISABLED_DuplicatedEdgeTest)
  {
  Graph g;
  EXPECT_TRUE (g.Connect (0, 1));
  EXPECT_TRUE (g.Connect (1, 2));
  EXPECT_TRUE (g.Connect (2, 3));

  EXPECT_FALSE (g.Connect (1, 0));
  EXPECT_FALSE (g.Connect (0, 1));
  EXPECT_FALSE (g.Connect (1, 2));
  EXPECT_FALSE (g.Connect (2, 1));
  EXPECT_FALSE (g.Connect (2, 3));
  EXPECT_FALSE (g.Connect (3, 2));
  }

/*
 * Test fixture for testing GraphMeasure class
 */
class DISABLED_GraphMeasureWithDuplicatedEdgeAddingTest : public ::testing::Test 
  {
  protected:
    virtual void SetUp ()
      {
      g.Connect (0, 2);
      g.Connect (0, 2); // duplicated edges are not counted
      g.Connect (2, 0); // duplicated edges are not counted
      g.Connect (2, 4);
      g.Connect (4, 8);
      g.Connect (8, 0);
      g.Connect (2, 8);
      g.Connect (0, 0); // no self-looping edges are allowed
      g.Connect (1, 1); // no self-looping edges are allowed
      }
  Graph g;
  };

/*
 * Test passed if the correct number of nodes in a graph is returned
 */
TEST_F (DISABLED_GraphMeasureWithDuplicatedEdgeAddingTest, NodeCountTest)
  {
  GraphMeasure gm (g);
  EXPECT_EQ (9, gm.NumberOfNodes ());
  }

/*
 * Test passed if the correct number of edges is a graph is returned
 */
TEST_F (DISABLED_GraphMeasureWithDuplicatedEdgeAddingTest, EdgeCountTest)
  {
  GraphMeasure gm (g);
  EXPECT_EQ (5, gm.NumberOfEdges ());
  }

class GetNeighborsOfTest : public ::testing::TestWithParam<uint>
  {};

TEST_P (GetNeighborsOfTest, NumberOfNeighborsAndNeighborIdTest)
  {
  Graph g;
  const uint n = GetParam ();
  RecordProperty("Number of nodes", n);
  for (uint adjv=1; adjv<=n; adjv++)
    {
    g.Connect (adjv, 0);
    }

  GraphMeasure gm (g);
  list<uint> all_adjv = gm.GetNeighborsOf (0);
  all_adjv.sort ();

  uint expected_v = 1;
  foreach (const uint& v, all_adjv) // (set<uint>::const_iterator it = all_adjv.begin (); it != all_adjv.end (); it++)
    {
    EXPECT_EQ (expected_v, v) << "number of nodes = " << n;
    expected_v++;
    }
  EXPECT_EQ (n, all_adjv.size ());
  for (uint v=1; v<=n; v++)
    {
    EXPECT_EQ (1, gm.GetNeighborsOf (v).size ()) << "v = " << v << ", number of nodes = " << n;
    }
  }

INSTANTIATE_TEST_CASE_P (NetSize, GetNeighborsOfTest, ::testing::Range<uint> (18, 20));

TEST (DisconnectTest, RemoveOneEdgeAdnOneEmptyTest)
  {
  Graph g;
  g.Connect (0,1);
  g.Connect (1,2);
  g.Connect (2,3);
  g.Connect (3,0);

  g.Disconnect (0, 2);
  g.Disconnect (0, 1);

  GraphMeasure gm (g);
  EXPECT_EQ (3, gm.NumberOfEdges ());
  }


TEST (DegreeOfTest, SimpleTest)
  {
  Graph g;
  g.Connect (0, 1);
  g.Connect (0, 2);
  g.Connect (0, 3);
  g.Connect (0, 4);
  g.Connect (0, 5);

  GraphMeasure gm (g);
  EXPECT_EQ (5, gm.DegreeOf (0));
  }

TEST (RandomIntTest, RandomIntTest)
  {  
  uint count = 0;
  for (uint i=0; i<10; i++)
    {
    while (RandomInt (10000) != 0) {count++;}
    cout << "random 0 occurs at " << count << " steps" << endl;
    }
  }
